Modern integrated circuit design has become an enormously complex problem. Issues such as timing, manufacturability, noise and crosstalk have become substantial hurdles for many designs. With physical effects having increasing impact on the behavior of integrated circuits, it becomes clear that the idealized “top-down” design flow has become impossible. For example, prediction of timing prior to placement has limited worth, as the correlation between such predictions and the post-placement timing has weakened. Thus, the incremental design paradigm has taken hold.
In an incremental design flow, emphasis is placed on iteratively performing analysis to determine problem areas, and re-executing parts of the design flow to correct these problems as they are identified. For instance, one might perform a placement, obtain some timing estimates, then insert buffers and re-do placement in order to improve timing.
Moreover, when placing the components of an electronic circuit, such as some standard cells instances, as part of the placement process in an integrated circuit digital design flow, a reiterative or incremental placement process is often used to analyze and resolve timing and design issues. For example, CAD (Computer Aided Design) tools may perform a placement, generate timing estimates, then insert buffers to improve timing. These tools are then re-run to perform another placement, timing analysis, and correction. In an incremental design flow, this iterative process of placement, analysis, correction and re-placement continues until timing and design closure is reached. A primary concern in this incremental placement flow is the minimization of perturbation (disturbance) of the prior placement. Specifically, if a new placement differs significantly from the previous placement, this difference can introduce additional timing problems, and the design flow may not converge to a satisfactory solution. Therefore, the most stable and satisfactory results are obtained when a new placement is produced that corrects timing problems and which differs minimally from the prior placement.
In the integrated circuit design literature, the search for an optimal or nearly optimal method, algorithm, or technique that creates new placements with minimal disturbance of the prior placement is referred to as a search for legal placements with minimized perturbation. This is a difficult challenge and prior attempts to find satisfactory incremental placement algorithms have had limited success.
Existing approaches to obtain placement legalization with perturbation minimization sometimes use flow-based techniques as a final placement step or, in an incremental placement flow, use simulated annealing, exhaustive search (branch-and-bound) and, more recently, diffusion-based placement techniques. One of the primary drawbacks of flow-based techniques is that these conventional flow-based techniques lack the capability of predicting perturbation which arises from cell movements. This lack of prediction in conventional flow-based legalization techniques often leads to inferior quality of placement results. Another limitation of flow-based methods is that they are applied once at a final placement stage and do not satisfactorily predict the movement of cells that will result from adding and removing cells from a placement.
Other existing approaches such as the simulated annealing, exhaustive search (branch-and-bound), and diffusion-based placement techniques are slow and inefficient (require more computer cycles) and do not result in new legalized placements that minimally disturb the prior placement.
Another approach utilizes the technique of network flow or greedy techniques. This approach tends to, however, miss a lot of opportunity to reduce perturbation by making somewhat arbitrary decision at the flow realization stage but not predicting such perturbation and are thus relatively inflexible. Another approach utilizes local search based methods. This approach wastes computational resources by examining many interesting possibilities.
Another school of conventional approaches is to utilize the placement techniques using the clumping algorithm. However, the conventional clumping algorithm as used in the conventional placement techniques does not provide incremental capabilities. Moreover, the conventional clumping algorithm approach is typically used as a touch-up final phase for the legalization rather than some tool which may be iteratively called and executed many times.
Another approach to address the problems described above is to use the diffusion-based technique. These approaches are, however, computationally expensive and inefficient and thus may be prohibitively expensive for incremental placement, since in an incremental design flow, incremental placement may be called and executed many times in an iterative fashion. The diffusion-based technique is also inflexible in the sense that it is more difficult to tune.